package maximumDifference;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;

public class Solution {
    public int maximumDifference(int[] nums) {
//        int ans = -1;
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = i+1; j < nums.length; j++) {
//                if(nums[i]<nums[j]){
//                    ans = Math.max(nums[j] - nums[i],ans);
//                }
//            }
//        }
//        return ans;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int ans = -1;
        for (int i = 1; i < nums.length; i++) {
            if(nums[i]>dp[i-1]){
                ans = Math.max(ans,nums[i] - dp[i-1]);
            }
            dp[i] = Math.min(dp[i-1],nums[i]);
        }
        return ans;
        // dp[i] 表示前i个数字中的最小值
    }
//    class Node{
//        int index;
//        int value;
//        public Node(int index,int value){
//            this.index = index;
//            this.value = value;
//        }
//    }
//    public int maximumDifference(int[] nums) {
//        Node[] nodes = new Node[nums.length];
//        for (int i = 0; i < nums.length; i++) {
//            nodes[i] = new Node(i,nums[i]);
//        }
//        Arrays.sort(nodes, (o1, o2) -> o1.value - o2.value);
//        int ans = -1;
//        for (int i = 0; i < nodes.length; i++) {
//            for (int j = i+1; j < nodes.length; j++) {
//                if(nodes[i].index<nodes[j].index&&nodes[i].value<nodes[j].value){
//                    ans = Math.max(ans,nodes[j].value - nodes[i].value);
//                }
//            }
//        }
//        return ans;
//    }
}
